package work.xiaohong.arithmetic.SortArithmetic;

import java.util.Arrays;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/26 0026 10:14
 * @description 冒泡排序
 *
 */
public class Bubble {
    /**
     * 排序原理
     * 1.比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
     * 2.对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
     *
     * 时间复杂度分析
     * 元素比较的次数
     * （N-1）+(N-2)+...+2+1 = ((N-1)+1)*N/2 = N^2/2-N/2
     * 元素的交换次数
     * （N-1）+(N-2)+...+2+1 = ((N-1)+1)*N/2 = N^2/2-N/2
     * 总执行次数
     * (N^2/2-N/2)+(N^2/2-N/2) = N^2-N
     * 所以时间复杂度为O(N^2)
     *
     * 稳定的排序算法
     */

    /**
     * 对数组内元素进行排序
     * @param arr
     */
    public static void bubbleSort(Comparable[] arr) {
        for (int i = arr.length-1; i > 0; i--) {  // 每次遍历的元素个数，第一次是全部，而后每次都将最大的元素放到了后面，所以每排一次遍历个数减一
            for (int j = 0; j < i; j++) {  // 从下标为0的位置开始比较并交换，直到边界
                if (SortUtils.greater(arr[j],arr[j+1])){  // 比较并交换
                    SortUtils.swap(arr,j,j+1);
                }
            }
        }
    }


}
